Games of Daze/Infomagic - Games of Daze (Summer 1995) (Disc 1 of 2).iso/x2ftp/msdos/theory/ifai_cyc/article.wf

Text File | 1995-03-25 | 27.1 KB | 540 lines

IF, AI, and the confabulating-arranger model of interactive fiction
by Jorn Barger ([e-mail])
September 26, 1994

Abstract: One plausible  design-paradigm for interactive fiction might
be to supply   IF authors with an   extensive library of   intelligent
objects that 'know' how to   interact realistically, including a  rich
model   of  human  behavior.  Doug  Lenat's   Cyc   project is already
attacking this task from a traditional AI perspective, but for IF this
knowledge may be  more simply collected  in the form of *stories*-- in
fact, a new mailinglist on the Internet is devoted to compiling such a
story-library.  If this library also  tags all the *most  interesting*
possible   plot-lines, the  computer's  task    might be  extended  to
"confabulating" the  player's  reality, on   the fly,   simultaneously
arranging both past  and  future so   as to open  as  many interesting
plot-directions as possible.


A  couple of issues ago (IED  7.4), Chris Crawford discussed the basic
known  'topologies'  for interactive fiction (IF)--   each of which he
showed to contain intractable fatal flaws.  Basically, *interactivity*
implies that the user is making choices,  which implies that the story
is  branching   into a  tree-like  topology.   But  Chris  showed that
storytrees must either be folded back on themselves in a very limiting
way, or have most of  their branches  trimmed to (violent)  dead-ends.
If  they   don't, they'll  necessarily    expand  exponentially...  so
consequently, within  these design paradigms, even high-budget efforts
are doomed to produce only simplistic and uninvolving games....

The fantasy for  the distant future, of  course, is  that the computer
should  offer an infinitely-various  Virtual Reality,  full of objects
and characters whose behavior mimics 'real  life' in great detail.  In
the  ideal future, one  should be  able  to step  into the  pages of a
Dickens or Tolstoy novel and interact with its characters as freely as
in 'real' life....

But how  do we get  there from  here  What sorts  of design strategies
might make these new forms of IF possible?

Certainly, one step in the right direction  will be to teach computers
the basic laws  by which real  objects  interact, which is  one of the
traditional challenges    of artificial intelligence   (AI).  In  this
article,  I'll first  explore the AI-world's  leading  contender for a
truly  intelligent program-- the  Cyc project.  Then  I'll look at how
Cyc's models overlap with those  of traditional text-adventure  games.
I'll discuss a potentially-simpler  strategy for compiling a 'Cyc' for
IF, using a text format called a "meta-story", and offer some examples
of how these  can capture knowledge  in an intuitive way.  And finally
I'll explore a new paradigm for IF-- the confabulating-arranger model.


The Cyc project as a universal knowledgebase

The last  thirty years  of academic AI   research have  produced  very
little  that computer-game designers  would find useful.  The problems
they've chosen to research have been too  limited, and the programming
structures they  seem   to  favor are   impossibly  slow for  realtime
gameplay.   So the world of  gaming has pretty much  had to invent its
own styles of AI, as it's needed them.

But for  the  last ten  years,  a highly   ambitious (and surprisingly
low-profile!) effort has been underway  in Austin, Texas, to spell out
the entire range of human commonsense knowledge. The  goal of this Cyc
(for enCYClopedia) project is a program that can read a newspaper, and
'understand' what  it  has read, well  enough to  detect violations of
common sense, just as  human readers can.  But  to the extent that  it
succeeds at *this*, it  should be equally useful,  at least in theory,
for maintaining internal consistency in a virtual world....

The Cyc team, led by Doug  Lenat, has been  trying to break down human
understanding   into   thousands    of  subdomains    that   they call
"micro-theories", like  ailments, food-preparation, communication, and
corporate behavior, and then trying to translate  the basic 'rules' of
each such domain into the language of  symbolic logic.  When they need
to  say,  "If someone   is  asphyxiating,  they cannot  breathe,"  for
example, they write:

(LogImplication
  (LogAnd
     (allInstancesOf $AIL Asphyxiation)
     (bodilyInvolved $AIL $AGT))
  (holdsIn $AIL
    (LogNot (behaviorCapable $AGT Breathing bodilyInvolved))))

where $AIL and $AGT are the variables for ailment and agent,
      LogAnd, LogNot, and LogImplication are simple logical connectives
and "holdsIn" defines the context within which this 'axiom' holds.

According to   the Cyc model,   if an  adventure game  needed  to know
what-happens-next at any particular point-- say, when a person drops a
delicate vase-- it would  send  a query  to Cyc and   in a matter   of
seconds, Cyc should  return with the news  that vases dropped on  hard
surfaces usually *shatter*...

Unfortunately, if you multiply that plausible retrieval-time times the
thousands or hundreds of thousands  of deductions that would be needed
to keep an interactive fiction realistic from moment to moment, you're
forced to the conclusion that  Cyc just isn't going  to be fast enough
to support IF, anytime soon.

Probably  the worst problem  here   is that Cyc--  unlike  *any* other
largescale project  in  history-- didn't  evolve  by  starting with  a
simpler  version   of   the whole,   and  gradually  filling   in  the
less-important  details.   Rather,  Cyc is   being built  by  the much
riskier strategy of accumulating   detailed subsections, one  by  one,
with *no known overall pattern*... and later streamlining it down to a
"core knowledge  base".  To  make that streamlined  enough  for IF may
turn out to be the hardest challenge of all!

So Cyc offers  a good startingpoint for IF-theory,  with regard to the
knowledge it hopes  to embody, but perhaps   not so good a model  with
regard to the performance constraints of realtime IF.  But we know for
certain that  some  level of  realtime    IF is possible--  Zork   and
Hitchhiker's Guide  (etc)  have proven  that!   But is there a  way to
build an "IF engine" that includes something more like Cyc?


Text-adventure development languages

The enduring  popularity of  text  adventures, especially  the Infocom
games of the early 1980s, has led a  number of talented enthusiasts to
create    programming   languages      especially  for  text-adventure
development.  Many of these are available free  on the Internet, where
the newsgroup rec.arts.int-fiction supports  a thriving subculture  of
text-adventure designers working in these formats.  (The newsgroup has
its archives at ftp.gmd.de in /if-archive/.)

TADS (The Text-Adventure Development System) by  Michael J. Roberts is
probably the  most popular environment,  because games created in TADS
can  be run on  almost every major  hardware platform.   TADS offers a
modest range  of predefined object-types  that have at least a minimal
level of intelligence    about their  own behavior.   Containers   and
vehicles, for example, understand that objects placed within them will
move with them, and will be  invisible unless the container or vehicle
is  transparent.  Characters automatically grow  hungry  if they don't
eat, and even eventually die.

TADS is object-oriented, with  the objects themselves  containing most
of the code embodying such "story elements":

class openable: container
    contentsReachable = { return( self.isopen ); }
    contentsVisible = { return( self.isopen ); }
    isopenable = true
    ldesc =
     { caps(); self.thedesc;
       if ( self.isopen )
       { " is open. ";
         pass ldesc;}
       else " is closed. "; }
[etc]

The TADS object-hierarchy is firmly grounded in story-telling pragmatics:

Thing
  Item: vehicle, surface, lightsource, key, food, container, clothing
  FixedItem: switch, dial, button, decoration, actor, chair
  Room

Cyc,  by contrast, offers at  the  highest level the following, rather
less pragmatic, partial object hierarchy:

Thing
  Intangible
  IndividualObject
    Event
    Stuff
      Process
        SomethingExisting
          TangibleObject


The Wisdom-FAQ mailinglist

If a knowledgebase like TADS's could be gradually extended, ultimately
even to the full extent targeted by Cyc, this  would surely be a major
step towards better  IF.  So with this  in  mind, a  group of  us from
rec.arts.int-fiction  (and elsewhere) have  spun off a new mailinglist
to  investigate the possibility  of  building a  sort of public-domain
'Cyc' for IF.

The  name for  the  mailinglist-- Wisdom  FAQ-- is   derived  from the
Internet tradition  of Frequently-Asked-Questions files  (FAQs), which
try to condense,  into the  most  accessible format possible, all  the
most *useful* information on any given topic.  The "Wisdom FAQ" can be
seen as a (rather  grandiose!)  image of a FAQ  that tries  to contain
*all* the wisdom of the world, on every  topic... starting, of course,
with those truths most useful  for interactive fiction.  (To subscribe
to  the list,  send  me  a request   at  [e-mail].   The
accumulated    archives can   be    ftp'd     from  ftp.mcs.com     in
mcsnet.users/jorn/wisdom/.   If you need me to  email them to you, let
me know how many kilobytes your emailbox can handle at once.)

The mailinglist is grappling simultaneously   with the task of  simply
accumulating 'story  elements' or axioms, and  the more difficult task
of agreeing on  a standardized way   of expressing them.   Because the
latter task is more technical and less interesting  to many people, it
will likely be spun off into a second list of its own sometime soon.

The task  of  enumerating story-elements, though,  is  not so  much  a
question  of  *technical* as  of  *storytelling*  expertise.  For this
reason, the Wisdom-list  eagerly welcomes  non-technical  contributors
who nevertheless have  a knack for spinning out  plotlines, or a  gift
for clever plot twists...


Every object tells a story... don't it?

The obvious way to  keep these collections of story-elements organized
is  according to which objects in   the object-hierarchy they require.
It's not *that* hard, for  any object in a game  (or in the world), to
rattle off the basic rules of its behavior.  One strategy for 'priming
your pump' might be to ask:

- Where does this object come from?
- How does a person come into relationship with it?
- How might the person use the object?
- How might they change it?
- How might they be changed by it?
- How might their relationship with it end?
- How might it cease to exist?

One convenient format  for  compiling the  answers  to these questions
might be called a "meta-story":

The food meta-story:  A person tended  a garden or farm raising plants
or animals to eat or sell.  They harvested  the food when the time was
right and sold it or preserved it or prepared it  and ate it or fed it
to friends or family.    If it was   well-prepared, their hunger   was
satisfied  and  they  were  happy.  The   food  travelled  thru  their
intestines and had to be  excreted.   If they  didn't get enough  good
food, they got thin and died.  Maybe the person preparing the food put
poison in  it to injure the  person  who ate it.   They might  have to
disguise the flavor of the poison.  Maybe  they prepared it poorly and
it tasted bad.

The bottle  meta-story: A person heated  up  some sand  in an oven and
blew air into it  with  a straw until it   became a bottle.  When   it
cooled, they could pour liquids into it and put a cork or cap on it to
keep the  liquids from spilling or  evaporating.  They could also fill
it by dipping it into a larger body of liquid. When they took the cork
out they could pour out the liquids, or drink from the bottle.  Two or
more people could pass the bottle around and share the drink.  If they
dropped  the bottle  on  something  hard, it probably   broke, and any
liquid in  it spilled out.  The broken  glass could cut a  person when
they touched it,  if they weren't careful.   It could make a  car tire
flat.  If  a barefoot person stepped  on it they would   get cut.  The
broken base might act like a lens to focus  light and start a fire, or
magnify something tiny. (The bottle with clear liquid in it might also
be a lens.)  The person  could knock  someone unconscious by  breaking
the bottle  over  their head.  They could  use  the bottleneck to make
their guitar  play better.  They  could roll dough   flat by using the
bottle like a rollingpin. (etc)


So one approach the Wisdom-list may use could  be to accumulate a sort
of 'children's encyclopedia' of  these meta-stories,  elaborating each
of them to whatever level of detail our creativity allows.

But simply  enriching  the   supply  of  intelligent   objects   won't
necessarily make the IF-author's job  easier.  For one thing, the more
pre-existing behavior that's been supplied for the game's objects, the
harder  it will  become for the  author to  anticipate  every possible
solution to the game's puzzles.  In fact, the  farther we move in this
direction, the less attractive the whole  idea of *puzzle-oriented IF*
begins to seem...


IF and 'psychology objects'

Cyc has  been circling closer and  closer to the  task of representing
*human dramas*, and claims already to have a working model of emotions
and  motivations,   but the Wisdom-list won't   stand  a chance  if it
doesn't directly confront the problem of encoding *literary* plots.

The  classic analysis of literary  plots is George Polti's "Thirty-Six
Dramatic    Situations".  Polti  analysed    a huge  range of  classic
plotlines  in  literature, and declared  these  to be the  basic ones:
Supplication, Deliverance, Revenge,  Vengeance by  Family upon Family,
Pursuit,  Victim of Cruelty  or  Misfortune, Disaster, Revolt,  Daring
Enterprise,   Abduction, Enigma, Obtaining,  Familial Hatred, Familial
Rivalry,  Murderous Adultery,  Madness, Fatal  Imprudence, Involuntary
Crimes of Love, Kinsman Kills Unrecognised Kinsman, Self Sacrifice for
an Ideal,   Self Sacrifice for Kindred,    All Sacrificed for Passion,
Sacrifice of  Loved  Ones,  Rivalry  Between Superior   and  Inferior,
Adultery,  Crimes of  Love,   Discovery of Dishonor  of  a  Loved One,
Obstacles to  Love,  An Enemy Loved,  Ambition,  Conflict with a  God,
Mistaken Jealousy, Faulty Judgement, Remorse, Recovery  of a Lost One,
Loss of Loved Ones

Only a few of  these will normally turn  up in the course of  applying
the meta-story approach to story *objects*, because the most important
'objects' in  literary plots tend  to  be  *psychological* ones,  like
emotions and motivations.

The meta-story approach can  still work fine as  a way of accumulating
story-elements,  though,  even  if   you choose  a   totally arbitrary
startingpoint  (for example, hypnosis), so  long as you're comfortable
with the storytelling aspect of things:

The 'hypnosis' meta-story:  Once a person  learned  they could control
others by hynosis.   So they hynotized  others into giving  away their
money and  power and their health and  their  self-respect.  And these
people didn't  even realize  what  had happened to  them.   Eventually
things got so bad they were desperate to discover  the source of their
situation.  Then one person got a glimpse  of the truth, and then lost
it, and then saw it again, and tried to tell others, and got dismissed
as crazy, and attacked, but finally figured  out how to lead others to
see the   truth,   and they rose  up   together   and overthrew  their
oppressors.

The intuitive familiarity of the  story-format allows almost any topic
to be productively explored...


Reverse-engineering emergent-behavior

While the artificial-life theorists have been hoping to discover a few
simple laws that will result in a vast  payoff of interesting stories,
via   the principle  of  'emergent behavior',  the meta-story approach
might be thought of as an attempt  to outdo them by 'cheating'-- first
you spell out the  stories you want to see  'emerge', and only then do
you analyse them and try to 'reverse engineer' the set of simpler laws
that will produce them.

So  even    something  as  simple as    Maslow's   hierarchy  of needs
(physiological,  safety,   belongingness and love,  esteem, cognitive,
aesthetic, and self-actualization needs),   which  might seem  like  a
plausible startingpoint  for a simple  set of  a-life laws, leading to
emergent behavior, reveals some extremely inobvious patterns (at least
from a mathematical point of view), when analysed for meta-stories:

The physiological-needs meta-story: Every  so  often, a person gets  a
craving to consume  food  and drink.  They  usually arrange  to have a
source  of these nearby,  that they can  rely on for purity.  They may
prepare the  food and drink,  cooking things, cutting them  up, mixing
them together, adding flavorings to make  the experience pleasant.  Or
maybe they  expect another person  to  do that for  them.  Usually,  a
group of people who live together will sit down together  to eat, at a
table  with plates and   silverware and glasses.   Afterwards, someone
must clean up.  Sometimes they may eat at restaurants, or in a vehicle
as they travel.  They may carry a container of water to drink (perhaps
flavored or  mixed  with nutrients or  stimulants  or intoxicants), or
stop at a vending machine or drinking fountain  or coffee machine.  If
a person's daily calories  consumed don't equal their calories burned,
they lose weight.  If they  consume more, they  gain weight.  If  they
lose too  much   weight, or  fail  to  drink   enough, they can   die.
Water-plus-wastes      is       excreted          by        urination,
food-after-nutrient-absorption by defecation.

The safety-needs meta-story:   A person felt  unsafe, and  they didn't
like   it.    Maybe there    were  other people  or   animals  around,
untrustworthy ones,  and their home  wasn't secure.  Maybe they had to
leave the safety of   their home  during the   day, and risked   being
attacked.  Maybe it  was nature that threatened  them, in the  form of
high cliffs, deep holes, quicksand, dangerous bodies of water, weather
that's too cold, hot, or violent, etc.  Maybe it was poorly maintained
technology that was the danger.  The person changed the environment or
changed their behavior  so that the danger was  lessened and they felt
safer.

The  belongingness-and-love-needs meta-story:  A  person felt  lonely.
They  sought out others' company and  acted charming  so they would be
welcome.  Or they acted domineering so that others  would be afraid to
reject them.  Or they acted hurt so that others pitied them.

The esteem-needs meta-story: A  person felt that  no one  respected or
appreciated them.   So they tried to  do something admirable, and then
made sure that others  knew about it.   Or maybe they lied about doing
something admirable.

The cognitive-needs meta-story: A person  needed to know something, or
was  just curious.  They  sought out a book and  read it, or a teacher
and took a  class or asked them questions.   Or they just observed the
thing they didn't understand, and thought deeply about it, maybe doing
experiments.  If they discovered something new they probably published
their findings.

The  esthetic-needs meta-story: A person  was oppressed by a boring or
ugly environment, so they made or  acquired or sought out objects that
were pleasing   to their senses.  Maybe they   recorded the process of
creation, so that  it could be  reexperienced later, by others.  Maybe
they positioned these creations within their environment so they could
experience them often.  Maybe they grew bored with them after a time.

The self-actualization-needs meta-story:  A person had everything they
needed,  but didn't feel fulfilled.  So  they looked within themselves
to discover what their heart wanted most, and followed their bliss...


"SimNormal"

Given the ambitious scope of  the Wisdom list,  there's a serious risk
of getting bogged down in such a mass of story-content, that one loses
any  sense of a   startingpoint, and so   also any chance  of actually
building a working IF program!

One way to keep these  meta-stories somewhat 'grounded in reality'  is
to visualize them as being acted out on  a computer screen, using even
the fairly  primitive existing standard  for  graphics adventures like
King's Quest and its ilk.  If  your stories are  too abstract for this
technology, you  probably  haven't thought   them  through in   enough
detail!

I like to imagine a sort of SimCity-like environment where a community
of  little  NPC's  go through  their  daily  routines   of  life, in a
completely   rote fashion,  *with no   emergent  behavior  expected or
desired*.   (In    honor  of Normal,   Illinois,   I  call this  world
"SimNormal".)

Looking again at  the belongingness-needs meta-story above, it's clear
that before you can visualize it as a SimNormal animation, you have to
break it  down further, according  to certain typical patterns  of how
these needs are satisfied:

The  casual-acquaintance meta-story: A person gets  to know another by
being introduced, or  by introducing themselves,  or by crossing paths
occasionally.  When  they   meet  they exchange  mild    greetings and
smalltalk about weather, news, gossip, entertainment they've seen.  If
nothing divisive turns up, they  may gradually open  up and trust each
other more.

The simplest  way  to encode  this might be  to  give  each  person an
intimacy-level    toward each other  one.     *Zero* would mean  total
strangers, but each time they noticed a given person it might increase
by  one.  When    it    reached    five,  say,  they'd     shift    to
casual-acquaintance  mode,   and  greet   each other.    If    they're
introduced, on the other hand,  they might reach  five right away.  As
this  number  continues to grow,   their  greetings should become more
extended in time, stopping to chat if they're  not in a hurry.  (There
could  be a   *chatting   animation* that's   designed to be    cycled
continually,  for  whatever  duration  they've  reached.)  Discovering
common  interests  may    cause  the   intimacy-level   to  skyrocket.
Discovering incompatibilities, or failing to see each other for a long
time, can cause the intimacy-level to drop.

The best-friend  meta-story: A person gradually  gets to  know someone
else,   and enjoys spending time  with  them. (Or  maybe it's a sudden
strong connection.)  They  arrange to spend  time  together, do things
together, maybe talk on the phone.  They tell each other their private
worries,  and try to help each  other.  These exchanges make them feel
better.  Sometimes  they fight,  and  reconcile or  not.  Maybe one of
them gets an S.O. and that causes them  to break apart.  Maybe it just
stops being so fun, and they drift apart.

A  person  may maintain   a 'short list'  of  those  with  the highest
intimacy rating, and when they're bored or upset they'll look to these
for support.  A  person-soothes-person2  story could be very  simple--
time is consumed  and person2 feels  better. (Person1  may or  may not
feel worse-- if they do, it bodes  ill for the friendship!)  There may
be a certain potential for conflict at each point, which should depend
on the   sorts  of personalities they   are,   and whether  they're in
competition for scarce resources.

The pals meta-story:  A person has one or  more best friends, and that
group grows larger as others are  allowed to join their get-togethers.
Maybe they're invited  or maybe they just show  up and tag  along.  If
someone doesn't  like them they may   be driven off.  Several  times a
week, at least, they arrange to  meet together.  Maybe there's a power
struggle between two  who both want  to lead.   Maybe one by  one they
drop out; maybe others take their places.

The planning-logistics of getting a group of free-thinking individuals
together are a lot more complex than for just  two.  Maybe any of them
can invite  the  others--  there'll  need to  be  be  a  'get-together
meta-story' to handle this.

The housemates meta-story: A person moves into a living-place with one
or more  housemates, sharing  common areas.  Usually,   the housemates
play  the role of  friends to some  degree,  listening to each others'
daily stories.  Some housemates are neater than  others, and this will
lead to conflicts.  When bills arrive, they sometimes have to be split
up unevenly and  this may cause  tensions.  One person is probably the
most responsible, signing  the checks, etc.   Each probably has one or
more annoying traits that *try* the patience of the others.  Maybe one
by one they move away, and  are replaced by others,  or maybe they all
leave at once.

The co-workers meta-story: A  person gets a job  at a  workplace, with
others.   Some   of   these become  friends,    others  maybe   casual
acquaintances.  Some become enemies.  Even when they fight, they still
have to work together, or quit, or ask for  a transfer.  Their enemies
may try to make them look bad to their bosses.


The confabulating-arranger model of IF

So if we  continue to pursue these directions  of research, what sorts
of IF might become possible?   How do you  give the player an infinite
world, and still   keep enough control to  involve  them in especially
interesting stories?

If  the computer 'knows'  all the most  interesting sorts of dramas in
literature, one strategy could  have it be  continually, unobtrusively
*revising* the virtual world  behind the scenes, so  as to open up  as
many interesting plotlines as possible.

So the game might open with a person  in their apartment, waking up in
the  morning, and if  they go  outdoors  they may be  presented with a
series of  neighbors whose dramas they can  become involved in...  but
none  of these dramas    needs to have   been  worked  out  in  detail
beforehand.   Rather, the computer   will continually  *improvise* new
possibilities based on  the player's choices, and  the view of reality
they've been allowed thus far.  If the player chooses not to follow up
any given  opening, that's no  problem...  there  will be  many  other
options to explore.

This way, the  past  is as *undetermined*  as  the future, and  can be
molded to any extent, limited only by what the player has already been
shown and  told.   So the computer  is  *actively* arranging that  new
developments   will  be as  interesting  as possible-- "confabulating"
reality, to use a psychiatric term.

And in this, the  "confabulating-arranger" model perhaps most  closely
resembles *the activity of the brain*, during *dreams*...!


Bibliography

Chris Crawford, "Flawed Methods for Interactive Storytelling" IED 7.4,
April 1994.
Douglas B. Lenat  and    R.V. Guha, "Building   Large  Knowledge-Based
Systems" Addison-Wesley 1991.
Michael J. Roberts, "TADS: The Text-Adventure Development System" Palo
Alto, High-Energy Software, 1992.
George Polti, "The Thirty-Six Dramatic Situations" Boston, The Writer,
1977 (originally published 1900).

Some journal references for more on Cyc:

"CYC" AI Magazine 7(1), 1986
"When will machines learn?" Machine Learning, Dec 1989
"Cyc: Toward Programs With Common Sense" CACM, Aug 1990
"Knowledge and Natural Language Processing" CACM, Aug 1990
"Common Sense and the Computer" Discover magazine, Aug 1990
"Cyc: A Mid-Term Report" AI Magazine, Fall 1990
"The commonsense reviews" Artificial Intelligence, 61(1), 1993
"CYC-O" Wired magazine, Apr 1994
"Enabling agents to work together" CACM, 37(7), 1994